Multi-stage Switching Networks have become an accepted means for interconnecting multiple devices within a computer system. Often systems require multiple paths through the switching networks to perform different functions. An earlier work at IBM by Peter Franaszek, as described in his work entitled "Path Hierarchies in Interconnection Networks" described two hierarchical paths for a network, one providing low-latency message transfer and the other providing guaranteed-delivery of a message transfer and the other providing guaranteed-delivery of a message at a longer latency. A message is attempted over the low-latency path first. If the transmission fails due to blocking or contention, it is retransmitted over the guaranteed-delivery path. This allows usually about 90% of the messages to be sent successfully over the low-latency path, and guarantees the delivery of a message that gets blocked on the low-latency path due to retransmissions.
U.S. Pat. No. 4,952,930 to P. A. Franaszek et al. issued Aug. 28, 1990 described the approach which used a second buffered path, which is in some ways similar to the current approach. However, it suffered by its requirements of a plurality of switches to implement it. While there would be no impediment to our adopting the teachings of this patent there remained a need for a simpler and yet more flexible approach to create a multi-stage network.
Multi-stage networks have become an accepted means for interconnecting multiple devices within a computer system. They are a replacement for the traditional crossbar interconnection. The crossbar is still a most efficient method of network interconnection, but it tends to be impractical for large systems. An N.times.M crossbar permits total simultaneous interconnection, where all the N devices can be communicating simultaneously with different members of the set of M devices. The crossbar is "non-blocking" because there nothing internal to the crossbar which prevents any given N device from connecting to an M device which is IDLE (is not connected to some other N device). If an N device desires to connect to an M device which is BUSY (previously connected to some other N device), no connection can be made until the previous connection is broken--however, this is referred to as "contention" and is not called "blocking".
When N and M become large (usually greater than 32 or 64) it becomes very unwieldy to build crossbars since their complexity increases at an N.times.M rate and their pin count increases at an (N.times.M).times.W rate, where W=the number of pins per port. Thus large networks are usually built from multi-stage networks constructed by cascading several stages of smaller crossbars together to provide an expanded network. The disadvantage of multi-stage networks is that they are "blocking", i.e., a connection might not be able to be made to an IDLE M device because there is no path available in the network to provide the necessary connection to the IDLE device.
Among other patents which might be reviewed are: U.S. Pat. No. 4,914,571 to A. E. Baratz et al. issued Apr. 3, 1990 which describes a method of addressing and thus how to find resources attached to a network, but does not deal with the hardware for the actual network itself.
U.S. Pat. No. 4,455,605 to R. L. Cormier et al. issued Jun. 19, 1984 which is for a bus oriented system, it is not a multi-stage network. Similarly, U.S. Pat. No. 4,396,984 to E. R. Videki, II issued Aug. 2, 1983 is for an I/O bus channel, not a multi-stage network. U.S. Pat. No. 4,570,261 to J. W. Maher issued Feb. 11, 1986 is for fault recovery over a bus oriented system, not a multi-stage network.
U.S. Pat. No. 4,207,609 to F. A. Luiz et al. issued Jun. 10, 1980 illustrates an I/O bus channel so that those in the art will understand the differences between the subject matter. It is not a multi-stage network.
U.S. Pat. No. 4,873,517 to A. E. Baratz et al. issued Oct. 10, 1989 is for a totally different type of network, not an equi-distant multi-stage network like that which we will describe, and also, U.S. Pat. No. 4,932,021 to T. S. Moody issued Jun. 5, 1990 for bus wiring paths inside a computer box, it is not a multi-stage network. U.S. Pat. No. 4,733,391 to R. J. Godbold et al. issued Mar. 22, 1988 illustrates a ring interconnection network, which is unlike a multi-stage network. U.S. Pat. No. 4,811,201 to B. R. Rau et al. issued Mar. 7, 1989 are not applicable to a multi-stage network. U.S. Pat. No. 4,754,395 to B. P Weisshaar et al. issued Jun. 28, 1988 is for a ring interconnection network.
We have solved some of the problems encountered in the prior art and will describe a way whereby some of the traditional blocking problems in multi-stage networks are circumvented.